// PowerSet.cpp
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// array [1, 2, 3]
// 什么是 array 的 Power Set 呢？
// array 所有的元素可以分裂出来的所有子数组的数组
// [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

// 编写一个函数，让它接受一个数组作为参数，并返回它的 power set。
vector<vector<int>> powerSet(vector<int> array) {
  // [1, 2, 3]
  // result [[]]
  // n = 1
  // length = 1
  // tmp [1]
  // result [[], [1]]

  // n = 2
  // length = 2
  // result[0] <- 2
  // result[1] <- 2
  // [[], [1], [2], [1, 2]]

  vector<vector<int>> result {{}};

  for (int n : array) {
    // n
    int length = result.size();

    for (int i = 0; i < length; ++i) {
      vector<int> tmp = result[i];
      tmp.push_back(n);

      result.push_back(tmp);
    }
  }

  return result;
}

int main(int argc, char const *argv[]) {
  /* code */
  vector<int> v {1, 2, 3};
  auto result = powerSet(v);

  for (vector<int> tmp : result) {
    cout<<"[";
    for (int n : tmp) {
      cout<<n<<",";
    }
    cout<<"]";
  }

  cout<<endl;
  return 0;
}
